package com.copa.l169;

/**
 * @author copa
 * @createDate 2022-05-20 10:43
 * @function 分治法
 */
public class Test3 {

    public int majorityElement(int[] nums) {
        // 分治
        return getMajority(nums, 0, nums.length - 1);
    }

    private int getMajority(int[] nums, int startIndex, int endIndex) {
        if (startIndex == endIndex) {
            // 如果此时开始指针等于结束指针，则直接返回任意一个即可
            return nums[startIndex];
        }
        int mid = startIndex + (endIndex - startIndex) / 2;
        // 左边拆分
        int leftMajority = getMajority(nums, startIndex, mid);
        // 右边拆分
        int rightMajority = getMajority(nums, mid + 1, endIndex);
        if (leftMajority == rightMajority) {
            // 若左边的众数等于右边的众数，直接返回任意一个即可
            return leftMajority;
        }
        // 若左边的众数不等于右边的众数，则需要根据[startIndex,endIndex]重新遍历，根据count的多少来抉择
        int leftCount = 0;
        int rightCount = 0;
        for (int i = startIndex; i <= endIndex; i++) {
            if (leftMajority == nums[i]) {
                leftCount++;
            } else if (rightMajority == nums[i]) {
                rightCount++;
            }
        }
        return leftCount > rightCount ? leftMajority : rightMajority;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{2,2,1,1,1,2,2};
        System.out.println(new Test3().majorityElement(nums));
    }
}
